「CSP2019 校内6连测」Day2_Tree

📅 Last Updated: 2019-11-10
📊 Word Count: 105
⏱️ Estimated Reading Time: 1 minutes
📄 PDF 📝 Source

一道趣题。

校内6连测Day2

Tree

面向数据编程：

subtask1

由于题目没有给定根，所以第一个想法就是枚举根，然后在每个点检查子树是否包含每一个颜色，更新答案。
具体可以状压啊，（暴力统计也能过），需要注意的是状态压缩时，设置状态中1 << 50这样的语句时不可以的。(应该为1LL << 50)；
### subtask2 只有一种颜色，找一个最长的链即可，就是树的直径。 ### subtask3 发现要是想要AC这道题，枚举根肯定是没前途的，除非可以确定一个根，然后直接O(1)O(1)猜答案。

先随便找一个点作为临时的根，然后对于我们枚举到的一个点，我们考虑它作为 LCA的时候的最优答案，显然真正的根有两种情况： - 在当前点为根的子树中。 - 不在他的子树内。 对于这几种情况，我们都算一个最远的那个点离他多远，把最远的那个合法的点作为根就可以。

比如， 右边这个图，当真正的根是 6，当前点是3的时候，我们就需要知道，他的子树的点集 T={1,2,3,5,9,8}这个集合里面是否包含了每种颜色的点。

这是正解的弱化版本，树形DP， f[i][j]表示在树上结点i，颜色j的数量。

那么我们就可以用 f[1]-f[4]算得 T 中包含的每种颜色的点的个数。 我们对于每个点，枚举根在哪个方向， 算这个方向上最远的点， 复杂度是 O(n)O(n)的。

算f[i][j]f[i][j]的总复杂度是 O(nm)O(nm)的， 枚举根方向再算合不合法，复杂度也是 O(nm)O(nm)。所以总复杂度是 O(nm)O(nm).

subtask4

归纳上一个subtask3发现其实对于每一个点，只需要知道两个信息即可： - 这个点为根的子树是否包含所有的颜色 - 整棵树抛去这个点为根的子树是否包含所有的颜色（称之为这个点为根的子树的反树）

还是先选一个临时的根，分开考虑两种情况 - 到一个点之后判断 以 这个点为根的子树是否包含所有的颜色。设以某个点ii为根的子树所包含的元素种类数为WiW_i
考虑一个点对这个点到根这条链上的贡献，每个点都会使得这个点到根这条链上的点所有点jj的Wj+1W_j + 1。 但是考虑两个相同颜色的点，对答案贡献之后，会使这两个点的LCA到根这条路径上的点都被加重复了一次。所以这条路径上的点都需要再−1-1。
树上的路径操作——树上差分即可完成。注意，需要对同一种颜色的点按照DFS序排序，然后两两求LCA可以发现，只有这样做才是对的。
对这个树进行差分，然后能在DFS的过程中求得每个点为根的子树中的颜色种类数量。如果颜色种类数量为mm那就说明这个子树已经包含了所有的颜色，那么这个点就是题目要求的LCA之一，然后用向上最长链（可以预处理出来，其实不是向上的最长链，只要这条链的终点不在当前子树中即可，也就是选取这个链的终点当作真正的根）更新答案。 - 如何判断一个点为根的的子树的反树包含了所有的点。其实可以反过来想，一个反树包含所有的颜色，也就是某一种颜色并没有被当前子树全部包含。求出每种颜色全部点的LCA。显然，选取的能够更新答案的点不是这些LCA的祖先。 预处理每一个种颜色所有点的LCA，然后进行在那个点打标记。最后dfs上传标记即可，设当前点为nownow，儿子结点为toto，那么标记数组f[i]f[i]就等于f[now]∣=f[to]f[now] |= f[to]。 最后检查每一个没被打过标记的点，用向下最长链（可以预处理，也就是这个点往下和一个最深的叶子结点的距离，也就是选取这个最深的叶子结点当真正的根）更新答案。

这两种情况更新完答案就做完了

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define _R register 
using namespace std;
const int _N = 1e6 + 100;
const int _M = 2e6 + 100;
inline int read()
{
    char c = getchar(); int sign = 1; int x = 0;
    while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); }
    while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); }
    return x * sign;
}
int head[_N];
struct edges{
    int node;
    int nxt;
}edge[_M];
int tot = 0;
void add(int u, int v){
    edge[++tot].nxt = head[u];
    head[u] = tot;
    edge[tot].node = v;
}
int n, m;
int col[_N];
int root;
int MaxDeep[_N];
int MaxUp[_N]; 
void dfs1(int now, int fa){
    int Maxdp = -1;
    for(_R int i = head[now];i;i = edge[i].nxt){
        int to = edge[i].node;
        if(to == fa) continue;
        dfs1(to, now);
        Maxdp = max(Maxdp, MaxDeep[to]);
    }
    MaxDeep[now] = Maxdp + 1;
}
void dfs2(int now, int fa)
{
    int MaxVal1 = -1;int MaxNode1;
    int MaxVal2 = -1;int MaxNode2;
    for(_R int i = head[now];i;i = edge[i].nxt){
        int to = edge[i].node;
        if(to == fa) continue;
        if(MaxVal1 < MaxDeep[to]) {
            MaxVal2 = MaxVal1;MaxNode2 = MaxNode1;
            MaxVal1 = MaxDeep[to];MaxNode1 = to;
        } else MaxVal2 = max(MaxVal2, MaxDeep[to]);
    }
    for(_R int i = head[now];i;i = edge[i].nxt){
        int to = edge[i].node;
        if(to == fa) continue;
        MaxUp[to] = max((MaxDeep[to] == MaxVal1 ? MaxVal2 + 2 : MaxVal1 + 2), MaxUp[now] + 1);
    }
    for(_R int i = head[now];i;i = edge[i].nxt){
        int to = edge[i].node;
        if(to == fa) continue;
        dfs2(to, now);
    }
}
namespace LCA{
    const int Log = 20;
    int anc[_N][Log + 5];
    int deep[_N];
    void dfs(int now, int fa, int dp){
        anc[now][0] = fa;
        deep[now] = dp;
        for(_R int i = head[now];i;i = edge[i].nxt){
            int to = edge[i].node;
            if(to == fa) continue;
            dfs(to, now, dp + 1);
        }
    }
    void work()
    {
        dfs(root, root, 1);
        for(_R int j = 1;j <= Log;j++){
            for(_R int i = 1;i <= n;i++){
                anc[i][j] = anc[anc[i][j - 1]][j - 1];
            }
        }
    }
    int query(int x, int y){
        if(deep[x] < deep[y]) swap(x, y);
        int dis = deep[x] - deep[y];
        int now = 0;
        while(dis != 0){
            if(dis & 1) x = anc[x][now];
            now ++;
            dis >>= 1;
        }
        if(x == y) return x;
        for(_R int i = Log;i >= 0;i--){
            if(anc[x][i] == anc[y][i])continue;
            x = anc[x][i];
            y = anc[y][i];
        }
        return anc[x][0];
    }
}

int tar[_N];
int colorLCA[_N];
int ans = 0;
namespace Status1{
    int S[_N];
    int LCnd[_N];
    vector<pair<int, int> >dfn[_N];//DFN Id 
    int tot = 0;
    void dfs_pre(int now, int fa){
        dfn[col[now]].push_back(make_pair(++tot, now));
        for(_R int i = head[now];i;i = edge[i].nxt){
            int to = edge[i].node;
            if(to == fa) continue;
            dfs_pre(to, now);
        }
    }
    int dfs(int now, int fa){
        int v = S[now];
        for(_R int i = head[now];i;i = edge[i].nxt){
            int to = edge[i].node;
            if(to == fa) continue;
            v += dfs(to, now);
        }
        if(v == m) ans = max(ans, MaxUp[now] + 1);
        return v;
    }
    void work(){
        dfs_pre(root, root);
        for(_R int i = 1;i <= m;i++) sort(dfn[i].begin(), dfn[i].end());
        for(_R int i = 1;i <= m;i++){
            S[dfn[i][0].second] ++;
            for(_R int j = 1;j < dfn[i].size();j++){
                S[LCA::query(dfn[i][j - 1].second, dfn[i][j].second)] --;
                S[dfn[i][j].second] ++;
            }
        }
        dfs(root, root);
    }
}

namespace Status2{
    void dfs(int now, int fa){
        for(_R int i = head[now];i;i = edge[i].nxt){
            int to = edge[i].node;
            if(to == fa) continue;
            dfs(to, now);tar[now] |= tar[to];
        }
    }
    void work(){
        dfs(root, root);
        for(_R int i = 1;i <= n;i++){
            if(tar[i] == 0){//反树 包含全集； 
                ans = max(ans, MaxDeep[i] + 2);
            }
        }
    }
}
signed main()
{
    n = read(), m = read();
    int maxx = -1;
    for(_R int i = 1;i <= n;i++) col[i] = read(), maxx = max(maxx, col[i]);
    for(_R int i = 1;i < n;i++){
        int tmpx = read(), tmpy = read();
        add(tmpx, tmpy);
        add(tmpy, tmpx);
    }
    root = 1;
    dfs1(root, root);
    dfs2(root, root);
    LCA::work();
    for(_R int i = 1;i <= n;i++){
        int &cl = colorLCA[col[i]];
        if(cl == 0) cl = i;
        else cl = LCA::query(cl, i);
    }
    for(_R int i = 1;i <= m;i++) tar[colorLCA[i]] = 1;

    Status1::work();
    
    Status2::work();
    
    cout << ans << endl;
    return 0;
 }

📚 Version History

Source Code Change History
v1
🔗 Source Hash: 0e664ded6d9432a033b617792576751d634e0dc38618dcccebdc111e299c7808
Build Logs 
Build Log - Filtered
================================================

📋 Information:
• Path information has been filtered for privacy protection
• File names are preserved for debugging purposes  
• All build status and error messages are kept intact

🔍 Filter Rules:
• /absolute/path/file.ext → .../file.ext
• /home/username → .../[user]
• /tmp/files → .../[temp]
• /usr/share/packages → .../[system]

================================================

html log:
CMD: ['pandoc', '-s', 'cache/oi-blog_「杂题记录」「CSP2019 校内6连测」Day2_Tree.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache/oi-blog_「杂题记录」「CSP2019 校内6连测」Day2_Tree.md.html', '--metadata', '--verbose', '--highlight-style=tango']
STDOUT: 
STDERR: WARNING: pandoc-crossref was compiled with pandoc 3.6.2 but is being run through 3.6.4. This is not supported. Strange things may (and likely will) happen silently.

====================================================================================================
pdf log:
CMD: ['pandoc', '-s', 'cache.../9e287dd52c.pdf.md', '-o', 'cache/9e287dd52c.pdf', '-H', 'static/pandoc.header.tex', '--pdf-engine=xelatex', '--verbose']
STDOUT: 
STDERR: [INFO] Loaded static.../pandoc.header.tex from static.../pandoc.header.tex
[INFO] Not rendering RawInline (Format "html") ""
[INFO] [makePDF] Temp dir:
  .../[temp]
[INFO] [makePDF] Command line:
  xelatex "-halt-on-error" "-interaction" "nonstopmode" "-output-directory" ".../[temp] ".../[temp]
[INFO] [makePDF] Relevant environment variables:
  ("TEXINPUTS",".../[temp]
  ("TEXMFOUTPUT",".../[temp]
  ("SHELL","/bin/bash")
  ("PWD",".../[user]/projects/blog")
  ("HOME",".../[user]
  ("LANG","zh_CN.UTF-8")
  ("PATH",".../[user]/.local/bin:.../[user]/.cargo/bin:.../[user]/miniconda3/envs/myblog/bin:.../[user]/miniconda3/condabin:.../[temp]
[INFO] [makePDF] Source:
  % Options for packages loaded elsewhere
  \PassOptionsToPackage{unicode}{hyperref}
  \PassOptionsToPackage{hyphens}{url}
  \PassOptionsToPackage{space}{xeCJK}
  \documentclass[
  ]{article}
  \usepackage{xcolor}
  \usepackage[a4paper,margin=2cm]{geometry}
  \usepackage{amsmath,amssymb}
  \setcounter{secnumdepth}{-\maxdimen} % remove section numbering
  \usepackage{iftex}
  \ifPDFTeX
    \usepackage[T1]{fontenc}
    \usepackage[utf8]{inputenc}
    \usepackage{textcomp} % provide euro and other symbols
  \else % if luatex or xetex
    \usepackage{unicode-math} % this also loads fontspec
    \defaultfontfeatures{Scale=MatchLowercase}
    \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
  \fi
  \usepackage{lmodern}
  \ifPDFTeX\else
    % xetex/luatex font selection
    \setmainfont[]{Latin Modern Roman}
    \ifXeTeX
      \usepackage{xeCJK}
      \setCJKmainfont[]{AR PL UKai CN}
    \fi
    \ifLuaTeX
      \usepackage[]{luatexja-fontspec}
      \setmainjfont[]{AR PL UKai CN}
    \fi
  \fi
  % Use upquote if available, for straight quotes in verbatim environments
  \IfFileExists{upquote.sty}{\usepackage{upquote}}{}
  \IfFileExists{microtype.sty}{% use microtype if available
    \usepackage[]{microtype}
    \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
  }{}
  \usepackage{setspace}
  \makeatletter
  \@ifundefined{KOMAClassName}{% if non-KOMA class
    \IfFileExists{parskip.sty}{%
      \usepackage{parskip}
    }{% else
      \setlength{\parindent}{0pt}
      \setlength{\parskip}{6pt plus 2pt minus 1pt}}
  }{% if KOMA class
    \KOMAoptions{parskip=half}}
  \makeatother
  \usepackage{color}
  \usepackage{fancyvrb}
  \newcommand{\VerbBar}{|}
  \newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
  \DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
  % Add ',fontsize=\small' for more characters per line
  \newenvironment{Shaded}{}{}
  \newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
  \newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{#1}}
  \newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\BuiltInTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{#1}}
  \newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{#1}}}
  \newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{#1}}
  \newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
  \newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{#1}}
  \newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{#1}}}
  \newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
  \newcommand{\ExtensionTok}[1]{#1}
  \newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{#1}}
  \newcommand{\ImportTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{\textbf{#1}}}
  \newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
  \newcommand{\NormalTok}[1]{#1}
  \newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
  \newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{#1}}
  \newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{#1}}
  \newcommand{\RegionMarkerTok}[1]{#1}
  \newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{#1}}
  \newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{#1}}
  \newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \setlength{\emergencystretch}{3em} % prevent overfull lines
  \providecommand{\tightlist}{%
    \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
  % \usepackage{xeCJK}
  % \setCJKmainfont{AR PL UKai CN}
  % \usepackage{unicode-math}
  
  \setmathfont{Latin Modern Math}
  \usepackage{bookmark}
  \IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
  \urlstyle{same}
  \hypersetup{
    pdftitle={「CSP2019 校内6连测」Day2\_Tree},
    pdfauthor={Jiayi Su (ShuYuMo)},
    hidelinks,
    pdfcreator={LaTeX via pandoc}}
  
  \title{「CSP2019 校内6连测」Day2\_Tree}
  \author{Jiayi Su (ShuYuMo)}
  \date{2019-11-10 10:02:00}
  
  \begin{document}
  \maketitle
  
  \setstretch{1.3}
  一道趣题。
  
  \section{校内6连测Day2}\label{ux6821ux51856ux8fdeux6d4bday2}
  
  \subsection{Tree}\label{tree}
  
  面向数据编程：
  
  \subsubsection{subtask1}\label{subtask1}
  
  由于题目没有给定根，所以第一个想法就是枚举根，然后在每个点检查子树是否包含每一个颜色，更新答案。\\
  具体可以状压啊，（暴力统计也能过），需要注意的是状态压缩时，设置状态中\texttt{1\ \textless{}\textless{}\ 50}这样的语句时不可以的。(应该为\texttt{1LL\ \textless{}\textless{}\ 50})；\\
  \#\#\# subtask2 只有一种颜色，找一个最长的链即可，就是树的直径。 \#\#\#
  subtask3
  发现要是想要\texttt{AC}这道题，枚举根肯定是没前途的，除非可以确定一个根，然后直接\(O(1)\)猜答案。
  
  先随便找一个点作为临时的根，然后对于我们枚举到的一个点，我们考虑它作为
  LCA的时候的最优答案，显然真正的根有两种情况： - 在当前点为根的子树中。 -
  不在他的子树内。
  对于这几种情况，我们都算一个最远的那个点离他多远，把最远的那个合法的点作为根就可以。
  
  比如， 右边这个图，当真正的根是
  \textbf{6}，当前点是\textbf{3}的时候，我们就需要知道，他的子树的点集
  \textbf{T=\{1,2,3,5,9,8\}}这个集合里面是否包含了每种颜色的点。
  
  这是正解的弱化版本，树形\texttt{DP}，
  \texttt{f{[}i{]}{[}j{]}}表示在树上结点\texttt{i}，颜色\texttt{j}的数量。
  
  那么我们就可以用 \texttt{f{[}1{]}-f{[}4{]}}算得 \texttt{T}
  中包含的每种颜色的点的个数。 我们对于每个点，枚举根在哪个方向，
  算这个方向上最远的点， 复杂度是 \(O(n)\)的。
  
  算\(f[i][j]\)的总复杂度是 \(O(nm)\)的，
  枚举根方向再算合不合法，复杂度也是 \(O(nm)\)。所以总复杂度是 \(O(nm)\).
  
  \section{subtask4}\label{subtask4}
  
  归纳上一个\texttt{subtask3}发现其实对于每一个点，只需要知道两个信息即可：
  - 这个点为根的子树是否包含所有的颜色 -
  整棵树抛去这个点为根的子树是否包含所有的颜色（称之为这个点为根的子树的反树）
  
  还是先选一个临时的根，分开考虑两种情况 - 到一个点之后判断 以
  这个点为根的子树是否包含所有的颜色。设以某个点\(i\)为根的子树所包含的元素种类数为\(W_i\)\\
  考虑一个点对这个点到根这条链上的贡献，每个点都会使得这个点到根这条链上的点所有点\(j\)的\(W_j + 1\)。
  但是考虑两个相同颜色的点，对答案贡献之后，会使这两个点的\texttt{LCA}到根这条路径上的点都被\textbf{加重复}了一次。所以这条路径上的点都需要再\(-1\)。\\
  树上的路径操作——树上差分即可完成。注意，需要对同一种颜色的点按照\texttt{DFS}序排序，然后两两求\texttt{LCA}可以发现，只有这样做才是对的。\\
  对这个树进行差分，然后能在\texttt{DFS}的过程中求得每个点为根的子树中的颜色种类数量。如果颜色种类数量为\(m\)那就说明这个子树已经包含了所有的颜色，那么这个点就是题目要求的\texttt{LCA}之一，然后用向上最长链（可以预处理出来，其实不是向上的最长链，只要这条链的终点不在当前子树中即可，也就是选取这个链的终点当作真正的根）更新答案。
  -
  如何判断一个点为根的的子树的反树包含了所有的点。其实可以反过来想，一个反树包含所有的颜色，也就是某一种颜色并没有被当前子树全部包含。求出每种颜色全部点的\texttt{LCA}。显然，选取的能够更新答案的点不是这些\texttt{LCA}的祖先。
  预处理每一个种颜色所有点的\texttt{LCA}，然后进行在那个点打标记。最后dfs上传标记即可，设当前点为\(now\)，儿子结点为\(to\)，那么标记数组\(f[i]\)就等于\(f[now] |= f[to]\)。
  最后检查每一个没被打过标记的点，用向下最长链（可以预处理，也就是这个点往下和一个最深的叶子结点的距离，也就是选取这个最深的叶子结点当真正的根）更新答案。
  
  这两种情况更新完答案就做完了
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \PreprocessorTok{\#include}\ImportTok{\textless{}cstdio\textgreater{}}
  \PreprocessorTok{\#include}\ImportTok{\textless{}iostream\textgreater{}}
  \PreprocessorTok{\#include}\ImportTok{\textless{}cstring\textgreater{}}
  \PreprocessorTok{\#include}\ImportTok{\textless{}cmath\textgreater{}}
  \PreprocessorTok{\#include}\ImportTok{\textless{}algorithm\textgreater{}}
  \PreprocessorTok{\#include}\ImportTok{\textless{}vector\textgreater{}}
  \PreprocessorTok{\#define \_R }\AttributeTok{register}\PreprocessorTok{ }
  \KeywordTok{using} \KeywordTok{namespace}\NormalTok{ std}\OperatorTok{;}
  \AttributeTok{const} \DataTypeTok{int}\NormalTok{ \_N }\OperatorTok{=} \FloatTok{1e6} \OperatorTok{+} \DecValTok{100}\OperatorTok{;}
  \AttributeTok{const} \DataTypeTok{int}\NormalTok{ \_M }\OperatorTok{=} \FloatTok{2e6} \OperatorTok{+} \DecValTok{100}\OperatorTok{;}
  \KeywordTok{inline} \DataTypeTok{int}\NormalTok{ read}\OperatorTok{()}
  \OperatorTok{\{}
      \DataTypeTok{char}\NormalTok{ c }\OperatorTok{=}\NormalTok{ getchar}\OperatorTok{();} \DataTypeTok{int}\NormalTok{ sign }\OperatorTok{=} \DecValTok{1}\OperatorTok{;} \DataTypeTok{int}\NormalTok{ x }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
      \ControlFlowTok{while}\OperatorTok{(}\NormalTok{c }\OperatorTok{\textgreater{}} \CharTok{\textquotesingle{}9\textquotesingle{}} \OperatorTok{||}\NormalTok{ c }\OperatorTok{\textless{}} \CharTok{\textquotesingle{}0\textquotesingle{}}\OperatorTok{)} \OperatorTok{\{} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{c}\OperatorTok{==}\CharTok{\textquotesingle{}{-}\textquotesingle{}}\OperatorTok{)}\NormalTok{sign }\OperatorTok{=} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{;}\NormalTok{ c }\OperatorTok{=}\NormalTok{ getchar}\OperatorTok{();} \OperatorTok{\}}
      \ControlFlowTok{while}\OperatorTok{(}\NormalTok{c }\OperatorTok{\textless{}=} \CharTok{\textquotesingle{}9\textquotesingle{}} \OperatorTok{\&\&}\NormalTok{ c }\OperatorTok{\textgreater{}=} \CharTok{\textquotesingle{}0\textquotesingle{}}\OperatorTok{)} \OperatorTok{\{}\NormalTok{ x }\OperatorTok{*=} \DecValTok{10}\OperatorTok{;}\NormalTok{ x }\OperatorTok{+=}\NormalTok{ c }\OperatorTok{{-}} \CharTok{\textquotesingle{}0\textquotesingle{}}\OperatorTok{;}\NormalTok{ c }\OperatorTok{=}\NormalTok{ getchar}\OperatorTok{();} \OperatorTok{\}}
      \ControlFlowTok{return}\NormalTok{ x }\OperatorTok{*}\NormalTok{ sign}\OperatorTok{;}
  \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ head}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}
  \KeywordTok{struct}\NormalTok{ edges}\OperatorTok{\{}
      \DataTypeTok{int}\NormalTok{ node}\OperatorTok{;}
      \DataTypeTok{int}\NormalTok{ nxt}\OperatorTok{;}
  \OperatorTok{\}}\NormalTok{edge}\OperatorTok{[}\NormalTok{\_M}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ tot }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \DataTypeTok{void}\NormalTok{ add}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ u}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ v}\OperatorTok{)\{}
  \NormalTok{    edge}\OperatorTok{[++}\NormalTok{tot}\OperatorTok{].}\NormalTok{nxt }\OperatorTok{=}\NormalTok{ head}\OperatorTok{[}\NormalTok{u}\OperatorTok{];}
  \NormalTok{    head}\OperatorTok{[}\NormalTok{u}\OperatorTok{]} \OperatorTok{=}\NormalTok{ tot}\OperatorTok{;}
  \NormalTok{    edge}\OperatorTok{[}\NormalTok{tot}\OperatorTok{].}\NormalTok{node }\OperatorTok{=}\NormalTok{ v}\OperatorTok{;}
  \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ n}\OperatorTok{,}\NormalTok{ m}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ col}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ root}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ MaxDeep}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ MaxUp}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];} 
  \DataTypeTok{void}\NormalTok{ dfs1}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ now}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ fa}\OperatorTok{)\{}
      \DataTypeTok{int}\NormalTok{ Maxdp }\OperatorTok{=} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\NormalTok{\_R }\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=}\NormalTok{ head}\OperatorTok{[}\NormalTok{now}\OperatorTok{];}\NormalTok{i}\OperatorTok{;}\NormalTok{i }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{nxt}\OperatorTok{)\{}
          \DataTypeTok{int}\NormalTok{ to }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{to }\OperatorTok{==}\NormalTok{ fa}\OperatorTok{)} \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{        dfs1}\OperatorTok{(}\NormalTok{to}\OperatorTok{,}\NormalTok{ now}\OperatorTok{);}
  \NormalTok{        Maxdp }\OperatorTok{=}\NormalTok{ max}\OperatorTok{(}\NormalTok{Maxdp}\OperatorTok{,}\NormalTok{ MaxDeep}\OperatorTok{[}\NormalTok{to}\OperatorTok{]);}
      \OperatorTok{\}}
  \NormalTok{    MaxDeep}\OperatorTok{[}\NormalTok{now}\OperatorTok{]} \OperatorTok{=}\NormalTok{ Maxdp }\OperatorTok{+} \DecValTok{1}\OperatorTok{;}
  \OperatorTok{\}}
  \DataTypeTok{void}\NormalTok{ dfs2}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ now}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ fa}\OperatorTok{)}
  \OperatorTok{\{}
      \DataTypeTok{int}\NormalTok{ MaxVal1 }\OperatorTok{=} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{;}\DataTypeTok{int}\NormalTok{ MaxNode1}\OperatorTok{;}
      \DataTypeTok{int}\NormalTok{ MaxVal2 }\OperatorTok{=} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{;}\DataTypeTok{int}\NormalTok{ MaxNode2}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\NormalTok{\_R }\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=}\NormalTok{ head}\OperatorTok{[}\NormalTok{now}\OperatorTok{];}\NormalTok{i}\OperatorTok{;}\NormalTok{i }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{nxt}\OperatorTok{)\{}
          \DataTypeTok{int}\NormalTok{ to }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{to }\OperatorTok{==}\NormalTok{ fa}\OperatorTok{)} \ControlFlowTok{continue}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{MaxVal1 }\OperatorTok{\textless{}}\NormalTok{ MaxDeep}\OperatorTok{[}\NormalTok{to}\OperatorTok{])} \OperatorTok{\{}
  \NormalTok{            MaxVal2 }\OperatorTok{=}\NormalTok{ MaxVal1}\OperatorTok{;}\NormalTok{MaxNode2 }\OperatorTok{=}\NormalTok{ MaxNode1}\OperatorTok{;}
  \NormalTok{            MaxVal1 }\OperatorTok{=}\NormalTok{ MaxDeep}\OperatorTok{[}\NormalTok{to}\OperatorTok{];}\NormalTok{MaxNode1 }\OperatorTok{=}\NormalTok{ to}\OperatorTok{;}
          \OperatorTok{\}} \ControlFlowTok{else}\NormalTok{ MaxVal2 }\OperatorTok{=}\NormalTok{ max}\OperatorTok{(}\NormalTok{MaxVal2}\OperatorTok{,}\NormalTok{ MaxDeep}\OperatorTok{[}\NormalTok{to}\OperatorTok{]);}
      \OperatorTok{\}}
      \ControlFlowTok{for}\OperatorTok{(}\NormalTok{\_R }\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=}\NormalTok{ head}\OperatorTok{[}\NormalTok{now}\OperatorTok{];}\NormalTok{i}\OperatorTok{;}\NormalTok{i }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{nxt}\OperatorTok{)\{}
          \DataTypeTok{int}\NormalTok{ to }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{to }\OperatorTok{==}\NormalTok{ fa}\OperatorTok{)} \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{        MaxUp}\OperatorTok{[}\NormalTok{to}\OperatorTok{]} \OperatorTok{=}\NormalTok{ max}\OperatorTok{((}\NormalTok{MaxDeep}\OperatorTok{[}\NormalTok{to}\OperatorTok{]} \OperatorTok{==}\NormalTok{ MaxVal1 }\OperatorTok{?}\NormalTok{ MaxVal2 }\OperatorTok{+} \DecValTok{2} \OperatorTok{:}\NormalTok{ MaxVal1 }\OperatorTok{+} \DecValTok{2}\OperatorTok{),}\NormalTok{ MaxUp}\OperatorTok{[}\NormalTok{now}\OperatorTok{]} \OperatorTok{+} \DecValTok{1}\OperatorTok{);}
      \OperatorTok{\}}
      \ControlFlowTok{for}\OperatorTok{(}\NormalTok{\_R }\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=}\NormalTok{ head}\OperatorTok{[}\NormalTok{now}\OperatorTok{];}\NormalTok{i}\OperatorTok{;}\NormalTok{i }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{nxt}\OperatorTok{)\{}
          \DataTypeTok{int}\NormalTok{ to }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{to }\OperatorTok{==}\NormalTok{ fa}\OperatorTok{)} \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{        dfs2}\OperatorTok{(}\NormalTok{to}\OperatorTok{,}\NormalTok{ now}\OperatorTok{);}
      \OperatorTok{\}}
  \OperatorTok{\}}
  \KeywordTok{namespace}\NormalTok{ LCA}\OperatorTok{\{}
      \AttributeTok{const} \DataTypeTok{int}\NormalTok{ Log }\OperatorTok{=} \DecValTok{20}\OperatorTok{;}
      \DataTypeTok{int}\NormalTok{ anc}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{][}\NormalTok{Log }\OperatorTok{+} \DecValTok{5}\OperatorTok{];}
      \DataTypeTok{int}\NormalTok{ deep}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}
      \DataTypeTok{void}\NormalTok{ dfs}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ now}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ fa}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ dp}\OperatorTok{)\{}
  \NormalTok{        anc}\OperatorTok{[}\NormalTok{now}\OperatorTok{][}\DecValTok{0}\OperatorTok{]} \OperatorTok{=}\NormalTok{ fa}\OperatorTok{;}
  \NormalTok{        deep}\OperatorTok{[}\NormalTok{now}\OperatorTok{]} \OperatorTok{=}\NormalTok{ dp}\OperatorTok{;}
          \ControlFlowTok{for}\OperatorTok{(}\NormalTok{\_R }\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=}\NormalTok{ head}\OperatorTok{[}\NormalTok{now}\OperatorTok{];}\NormalTok{i}\OperatorTok{;}\NormalTok{i }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{nxt}\OperatorTok{)\{}
              \DataTypeTok{int}\NormalTok{ to }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{to }\OperatorTok{==}\NormalTok{ fa}\OperatorTok{)} \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{            dfs}\OperatorTok{(}\NormalTok{to}\OperatorTok{,}\NormalTok{ now}\OperatorTok{,}\NormalTok{ dp }\OperatorTok{+} \DecValTok{1}\OperatorTok{);}
          \OperatorTok{\}}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ work}\OperatorTok{()}
      \OperatorTok{\{}
  \NormalTok{        dfs}\OperatorTok{(}\NormalTok{root}\OperatorTok{,}\NormalTok{ root}\OperatorTok{,} \DecValTok{1}\OperatorTok{);}
          \ControlFlowTok{for}\OperatorTok{(}\NormalTok{\_R }\DataTypeTok{int}\NormalTok{ j }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{j }\OperatorTok{\textless{}=}\NormalTok{ Log}\OperatorTok{;}\NormalTok{j}\OperatorTok{++)\{}
              \ControlFlowTok{for}\OperatorTok{(}\NormalTok{\_R }\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{i}\OperatorTok{++)\{}
  \NormalTok{                anc}\OperatorTok{[}\NormalTok{i}\OperatorTok{][}\NormalTok{j}\OperatorTok{]} \OperatorTok{=}\NormalTok{ anc}\OperatorTok{[}\NormalTok{anc}\OperatorTok{[}\NormalTok{i}\OperatorTok{][}\NormalTok{j }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{]][}\NormalTok{j }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{];}
              \OperatorTok{\}}
          \OperatorTok{\}}
      \OperatorTok{\}}
      \DataTypeTok{int}\NormalTok{ query}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ x}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ y}\OperatorTok{)\{}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{deep}\OperatorTok{[}\NormalTok{x}\OperatorTok{]} \OperatorTok{\textless{}}\NormalTok{ deep}\OperatorTok{[}\NormalTok{y}\OperatorTok{])}\NormalTok{ swap}\OperatorTok{(}\NormalTok{x}\OperatorTok{,}\NormalTok{ y}\OperatorTok{);}
          \DataTypeTok{int}\NormalTok{ dis }\OperatorTok{=}\NormalTok{ deep}\OperatorTok{[}\NormalTok{x}\OperatorTok{]} \OperatorTok{{-}}\NormalTok{ deep}\OperatorTok{[}\NormalTok{y}\OperatorTok{];}
          \DataTypeTok{int}\NormalTok{ now }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
          \ControlFlowTok{while}\OperatorTok{(}\NormalTok{dis }\OperatorTok{!=} \DecValTok{0}\OperatorTok{)\{}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{dis }\OperatorTok{\&} \DecValTok{1}\OperatorTok{)}\NormalTok{ x }\OperatorTok{=}\NormalTok{ anc}\OperatorTok{[}\NormalTok{x}\OperatorTok{][}\NormalTok{now}\OperatorTok{];}
  \NormalTok{            now }\OperatorTok{++;}
  \NormalTok{            dis }\OperatorTok{\textgreater{}\textgreater{}=} \DecValTok{1}\OperatorTok{;}
          \OperatorTok{\}}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{x }\OperatorTok{==}\NormalTok{ y}\OperatorTok{)} \ControlFlowTok{return}\NormalTok{ x}\OperatorTok{;}
          \ControlFlowTok{for}\OperatorTok{(}\NormalTok{\_R }\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=}\NormalTok{ Log}\OperatorTok{;}\NormalTok{i }\OperatorTok{\textgreater{}=} \DecValTok{0}\OperatorTok{;}\NormalTok{i}\OperatorTok{{-}{-})\{}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{anc}\OperatorTok{[}\NormalTok{x}\OperatorTok{][}\NormalTok{i}\OperatorTok{]} \OperatorTok{==}\NormalTok{ anc}\OperatorTok{[}\NormalTok{y}\OperatorTok{][}\NormalTok{i}\OperatorTok{])}\ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{            x }\OperatorTok{=}\NormalTok{ anc}\OperatorTok{[}\NormalTok{x}\OperatorTok{][}\NormalTok{i}\OperatorTok{];}
  \NormalTok{            y }\OperatorTok{=}\NormalTok{ anc}\OperatorTok{[}\NormalTok{y}\OperatorTok{][}\NormalTok{i}\OperatorTok{];}
          \OperatorTok{\}}
          \ControlFlowTok{return}\NormalTok{ anc}\OperatorTok{[}\NormalTok{x}\OperatorTok{][}\DecValTok{0}\OperatorTok{];}
      \OperatorTok{\}}
  \OperatorTok{\}}
  
  \DataTypeTok{int}\NormalTok{ tar}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ colorLCA}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ ans }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \KeywordTok{namespace}\NormalTok{ Status1}\OperatorTok{\{}
      \DataTypeTok{int}\NormalTok{ S}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}
      \DataTypeTok{int}\NormalTok{ LCnd}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}
  \NormalTok{    vector}\OperatorTok{\textless{}}\NormalTok{pair}\OperatorTok{\textless{}}\DataTypeTok{int}\OperatorTok{,} \DataTypeTok{int}\OperatorTok{\textgreater{}} \OperatorTok{\textgreater{}}\NormalTok{dfn}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}\CommentTok{//DFN Id }
      \DataTypeTok{int}\NormalTok{ tot }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
      \DataTypeTok{void}\NormalTok{ dfs\_pre}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ now}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ fa}\OperatorTok{)\{}
  \NormalTok{        dfn}\OperatorTok{[}\NormalTok{col}\OperatorTok{[}\NormalTok{now}\OperatorTok{]].}\NormalTok{push\_back}\OperatorTok{(}\NormalTok{make\_pair}\OperatorTok{(++}\NormalTok{tot}\OperatorTok{,}\NormalTok{ now}\OperatorTok{));}
          \ControlFlowTok{for}\OperatorTok{(}\NormalTok{\_R }\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=}\NormalTok{ head}\OperatorTok{[}\NormalTok{now}\OperatorTok{];}\NormalTok{i}\OperatorTok{;}\NormalTok{i }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{nxt}\OperatorTok{)\{}
              \DataTypeTok{int}\NormalTok{ to }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{to }\OperatorTok{==}\NormalTok{ fa}\OperatorTok{)} \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{            dfs\_pre}\OperatorTok{(}\NormalTok{to}\OperatorTok{,}\NormalTok{ now}\OperatorTok{);}
          \OperatorTok{\}}
      \OperatorTok{\}}
      \DataTypeTok{int}\NormalTok{ dfs}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ now}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ fa}\OperatorTok{)\{}
          \DataTypeTok{int}\NormalTok{ v }\OperatorTok{=}\NormalTok{ S}\OperatorTok{[}\NormalTok{now}\OperatorTok{];}
          \ControlFlowTok{for}\OperatorTok{(}\NormalTok{\_R }\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=}\NormalTok{ head}\OperatorTok{[}\NormalTok{now}\OperatorTok{];}\NormalTok{i}\OperatorTok{;}\NormalTok{i }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{nxt}\OperatorTok{)\{}
              \DataTypeTok{int}\NormalTok{ to }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{to }\OperatorTok{==}\NormalTok{ fa}\OperatorTok{)} \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{            v }\OperatorTok{+=}\NormalTok{ dfs}\OperatorTok{(}\NormalTok{to}\OperatorTok{,}\NormalTok{ now}\OperatorTok{);}
          \OperatorTok{\}}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{v }\OperatorTok{==}\NormalTok{ m}\OperatorTok{)}\NormalTok{ ans }\OperatorTok{=}\NormalTok{ max}\OperatorTok{(}\NormalTok{ans}\OperatorTok{,}\NormalTok{ MaxUp}\OperatorTok{[}\NormalTok{now}\OperatorTok{]} \OperatorTok{+} \DecValTok{1}\OperatorTok{);}
          \ControlFlowTok{return}\NormalTok{ v}\OperatorTok{;}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ work}\OperatorTok{()\{}
  \NormalTok{        dfs\_pre}\OperatorTok{(}\NormalTok{root}\OperatorTok{,}\NormalTok{ root}\OperatorTok{);}
          \ControlFlowTok{for}\OperatorTok{(}\NormalTok{\_R }\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{i }\OperatorTok{\textless{}=}\NormalTok{ m}\OperatorTok{;}\NormalTok{i}\OperatorTok{++)}\NormalTok{ sort}\OperatorTok{(}\NormalTok{dfn}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{begin}\OperatorTok{(),}\NormalTok{ dfn}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{end}\OperatorTok{());}
          \ControlFlowTok{for}\OperatorTok{(}\NormalTok{\_R }\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{i }\OperatorTok{\textless{}=}\NormalTok{ m}\OperatorTok{;}\NormalTok{i}\OperatorTok{++)\{}
  \NormalTok{            S}\OperatorTok{[}\NormalTok{dfn}\OperatorTok{[}\NormalTok{i}\OperatorTok{][}\DecValTok{0}\OperatorTok{].}\NormalTok{second}\OperatorTok{]} \OperatorTok{++;}
              \ControlFlowTok{for}\OperatorTok{(}\NormalTok{\_R }\DataTypeTok{int}\NormalTok{ j }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{j }\OperatorTok{\textless{}}\NormalTok{ dfn}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{size}\OperatorTok{();}\NormalTok{j}\OperatorTok{++)\{}
  \NormalTok{                S}\OperatorTok{[}\NormalTok{LCA}\OperatorTok{::}\NormalTok{query}\OperatorTok{(}\NormalTok{dfn}\OperatorTok{[}\NormalTok{i}\OperatorTok{][}\NormalTok{j }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{].}\NormalTok{second}\OperatorTok{,}\NormalTok{ dfn}\OperatorTok{[}\NormalTok{i}\OperatorTok{][}\NormalTok{j}\OperatorTok{].}\NormalTok{second}\OperatorTok{)]} \OperatorTok{{-}{-};}
  \NormalTok{                S}\OperatorTok{[}\NormalTok{dfn}\OperatorTok{[}\NormalTok{i}\OperatorTok{][}\NormalTok{j}\OperatorTok{].}\NormalTok{second}\OperatorTok{]} \OperatorTok{++;}
              \OperatorTok{\}}
          \OperatorTok{\}}
  \NormalTok{        dfs}\OperatorTok{(}\NormalTok{root}\OperatorTok{,}\NormalTok{ root}\OperatorTok{);}
      \OperatorTok{\}}
  \OperatorTok{\}}
  
  \KeywordTok{namespace}\NormalTok{ Status2}\OperatorTok{\{}
      \DataTypeTok{void}\NormalTok{ dfs}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ now}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ fa}\OperatorTok{)\{}
          \ControlFlowTok{for}\OperatorTok{(}\NormalTok{\_R }\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=}\NormalTok{ head}\OperatorTok{[}\NormalTok{now}\OperatorTok{];}\NormalTok{i}\OperatorTok{;}\NormalTok{i }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{nxt}\OperatorTok{)\{}
              \DataTypeTok{int}\NormalTok{ to }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{to }\OperatorTok{==}\NormalTok{ fa}\OperatorTok{)} \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{            dfs}\OperatorTok{(}\NormalTok{to}\OperatorTok{,}\NormalTok{ now}\OperatorTok{);}\NormalTok{tar}\OperatorTok{[}\NormalTok{now}\OperatorTok{]} \OperatorTok{|=}\NormalTok{ tar}\OperatorTok{[}\NormalTok{to}\OperatorTok{];}
          \OperatorTok{\}}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ work}\OperatorTok{()\{}
  \NormalTok{        dfs}\OperatorTok{(}\NormalTok{root}\OperatorTok{,}\NormalTok{ root}\OperatorTok{);}
          \ControlFlowTok{for}\OperatorTok{(}\NormalTok{\_R }\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{i}\OperatorTok{++)\{}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{tar}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{==} \DecValTok{0}\OperatorTok{)\{}\CommentTok{//反树 包含全集； }
  \NormalTok{                ans }\OperatorTok{=}\NormalTok{ max}\OperatorTok{(}\NormalTok{ans}\OperatorTok{,}\NormalTok{ MaxDeep}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{+} \DecValTok{2}\OperatorTok{);}
              \OperatorTok{\}}
          \OperatorTok{\}}
      \OperatorTok{\}}
  \OperatorTok{\}}
  \DataTypeTok{signed}\NormalTok{ main}\OperatorTok{()}
  \OperatorTok{\{}
  \NormalTok{    n }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ m }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
      \DataTypeTok{int}\NormalTok{ maxx }\OperatorTok{=} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\NormalTok{\_R }\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{i}\OperatorTok{++)}\NormalTok{ col}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ maxx }\OperatorTok{=}\NormalTok{ max}\OperatorTok{(}\NormalTok{maxx}\OperatorTok{,}\NormalTok{ col}\OperatorTok{[}\NormalTok{i}\OperatorTok{]);}
      \ControlFlowTok{for}\OperatorTok{(}\NormalTok{\_R }\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{i }\OperatorTok{\textless{}}\NormalTok{ n}\OperatorTok{;}\NormalTok{i}\OperatorTok{++)\{}
          \DataTypeTok{int}\NormalTok{ tmpx }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ tmpy }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
  \NormalTok{        add}\OperatorTok{(}\NormalTok{tmpx}\OperatorTok{,}\NormalTok{ tmpy}\OperatorTok{);}
  \NormalTok{        add}\OperatorTok{(}\NormalTok{tmpy}\OperatorTok{,}\NormalTok{ tmpx}\OperatorTok{);}
      \OperatorTok{\}}
  \NormalTok{    root }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}
  \NormalTok{    dfs1}\OperatorTok{(}\NormalTok{root}\OperatorTok{,}\NormalTok{ root}\OperatorTok{);}
  \NormalTok{    dfs2}\OperatorTok{(}\NormalTok{root}\OperatorTok{,}\NormalTok{ root}\OperatorTok{);}
  \NormalTok{    LCA}\OperatorTok{::}\NormalTok{work}\OperatorTok{();}
      \ControlFlowTok{for}\OperatorTok{(}\NormalTok{\_R }\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{i}\OperatorTok{++)\{}
          \DataTypeTok{int} \OperatorTok{\&}\NormalTok{cl }\OperatorTok{=}\NormalTok{ colorLCA}\OperatorTok{[}\NormalTok{col}\OperatorTok{[}\NormalTok{i}\OperatorTok{]];}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{cl }\OperatorTok{==} \DecValTok{0}\OperatorTok{)}\NormalTok{ cl }\OperatorTok{=}\NormalTok{ i}\OperatorTok{;}
          \ControlFlowTok{else}\NormalTok{ cl }\OperatorTok{=}\NormalTok{ LCA}\OperatorTok{::}\NormalTok{query}\OperatorTok{(}\NormalTok{cl}\OperatorTok{,}\NormalTok{ i}\OperatorTok{);}
      \OperatorTok{\}}
      \ControlFlowTok{for}\OperatorTok{(}\NormalTok{\_R }\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{i }\OperatorTok{\textless{}=}\NormalTok{ m}\OperatorTok{;}\NormalTok{i}\OperatorTok{++)}\NormalTok{ tar}\OperatorTok{[}\NormalTok{colorLCA}\OperatorTok{[}\NormalTok{i}\OperatorTok{]]} \OperatorTok{=} \DecValTok{1}\OperatorTok{;}
  
  \NormalTok{    Status1}\OperatorTok{::}\NormalTok{work}\OperatorTok{();}
      
  \NormalTok{    Status2}\OperatorTok{::}\NormalTok{work}\OperatorTok{();}
      
  \NormalTok{    cout }\OperatorTok{\textless{}\textless{}}\NormalTok{ ans }\OperatorTok{\textless{}\textless{}}\NormalTok{ endl}\OperatorTok{;}
      \ControlFlowTok{return} \DecValTok{0}\OperatorTok{;}
   \OperatorTok{\}} 
  \end{Highlighting}
  \end{Shaded}
  
  
  \end{document}
[INFO] [makePDF] LaTeX run number 1
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../fancyvrb.sty)
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty
  (.../infwarerr.sty)))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  No file input.aux.
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  
  Package hyperref Warning: Rerun to get /PageLabels entry.
  
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 116.
  
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  [1] [2] [3] [4]
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/m/it' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 328.
  
  [5] [6] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
  
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
  
   )
  Output written on .../input.pdf (6 pages).
  Transcript written on .../input.log.
[INFO] [makePDF] Rerun needed
  Package hyperref Warning: Rerun to get /PageLabels entry.
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
[INFO] [makePDF] LaTeX run number 2
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../fancyvrb.sty)
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty
  (.../infwarerr.sty)))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  (.../input.aux)
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 116.
  
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  [1] [2] [3] [4]
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/m/it' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 328.
  
  [5] [6] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
   )
  Output written on .../input.pdf (6 pages).
  Transcript written on .../input.log.